1. Technical Field
The present invention relates generally to an improved data processing system and in particular to a method and apparatus for representing billing and functions. Still more particularly, the present invention relates to a method and apparatus for representing boolean functions using binary decision diagrams.
2. Description of Related Art
In designing circuits, many types of elements may be used in logic design and synthesis of circuits. Typically, these circuits include various components, such as, for example, gates and latches. In analyzing and manipulating these structures, the various elements are typically represented as nodes in a binary decision diagram (BDD). These BDD""s are widely used as a data structure for representing boolean expressions in design automation tools. These BDD""s have emerged as the representation of choice for many other applications, including digital circuit design. Many formal verification techniques, including model checking, equivalence checking, optimization of combinatorial circuits, and test pattern generation, have a fundamental reliance on BDD""s and their implementations. These type of diagrams have a disadvantage in that they grow very large very quickly. For example, using a BDD to represent a 16-bit multiplexer takes one half of a gigabyte of memory. With these increasing trends towards increased design complexity, an even greater demand on improving memory requirements for BDD""s is present. Generally, memory requirements for BDD""s grow exponentially with the number of boolean variables. Numerous improvements have been made on BDD structures, such as the efficient BDD package by Randall Bryant as described in Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, C-35 August 1998, pgs. 677-691. Even with improvements, memory requirements still pose a limiting factor to the use of BDD""s for large diagrams. For example, in model checking, the BDD memory requirements have made it impossible to verify a full chip of any significant function in its entirety.
In an effort to reduce the amount of memory used by a BDD representation of a chip, compression of these diagrams have been used. Compression presently used may yield anywhere from a 2xc3x97 to 10xc3x97 reduction in many practical cases, excluding those in which data is statistically uniformly distributed, which is a rare situation. Lossless compression, however, renders the data unusable for random access. As a result, such compression is typically used only towards keeping data compressed for archival purposes and not for use during computation as in the case of BDD data.
Therefore, it would be advantageous to have an improved method and apparatus for compressing and manipulating BDD data in a manner that random access of the BDD data is provided.
The present invention provides a method and apparatus in a data processing system for manipulating a set of binary decision diagrams. A plurality of segments is created from the set of binary decision diagrams. A group of compression codes is associated with the set of segments, wherein the group of compression codes form a compressed data structure representing the set of binary decision diagrams.